A Cyclic Redundancy Code (CRC) is a means by which the integrity of data communications and storage can be verified. The unit of data to be validated may be as small as eight bits or as large as several thousand bytes. The most common of these data transfer applications is the "hard" and "floppy" disk storage devices which are a part of nearly every computer system. Another use of a CRC is in the transmission of data from one computer system to another. Still another use of a CRC is in validating the contents of Read Only Memory (ROM) which contains the kernel of an operating system and/or the code which is executed when a computer has power applied to it. Often, this ROM code is checked as a part of a power up test sequence. The lengths of the most common CRC codes are eight and sixteen bits. CRC-32 is a 32 bit code which increases the number of bits of data that can be verified with one CRC.
A binary polynomial is a polynomial in which all coefficients are either one or zero. A CRC is generated by dividing data to be validated by a predetermined binary polynomial prior to storage or transmission. The remainder from the division operation is the CRC or "checksum", and this code is usually appended to the data to be validated. For validation, the data with the appended CRC is divided again by the same polynomial. If the data is unchanged, a zero remainder will result. Anything other than a zero remainder indicates that the data has been corrupted.
The following example illustrates the calculation and use of a CRC: ##EQU1## where the "+" denotes the exclusive-OR operation (division is done in modulo 2 arithmetic which is simply the exclusive-OR operation). In modulo 2 arithmetic, addition is the same as subtraction. Using this property: EQU 2.sup.k M+R=QP
2.sup.k M+R is simply the shifted data with the remainder appended. It will be noted that both sides of the equation are evenly divisible by the predetermined polynomial, P. The shifted data plus the remainder is what is transmitted or stored. When the data, including the remainder, is again divided by the polynomial, the remainder will be zero if the data and checksum are unchanged.
With the data given above: ##STR1##
The checking operation will take (2.sup.k M)+R and divide it by the same generating polynomial P. ##STR2##
As expected, a zero remainder is obtained indicating no error in the transmission of the data.
CRCs can detect a large number of errors including:
all one or two bit errors; PA1 all odd numbers of bit errors; PA1 all burst errors less than the degree of the predetermined polynomial; and PA1 most burst errors greater than the degree of the predetermined polynomial.
CRC polynomials in common use today include:
______________________________________ CRC-16 X.sup.16 + X.sup.15 + X.sup.2 + X.sup.0 SDLC (IBM, CCITT) X.sup.16 + X.sup.12 + X.sup.5 + X.sup.0 CRC-12 X.sup.12 + X.sup.11 + X.sup.3 + X.sup.2 + X.sup.1 + X.sup.0 CRC-16 Reverse X.sup.16 + X.sup.14 + X.sup.1 + X.sup.0 SDLC Reverse X.sup.16 + X.sup.11 + X.sup.4 + X.sup.0 LRCC-16 X.sup.16 + X.sup.0 LRCC-8 X.sup.8 + X.sup.0 ______________________________________
Those skilled in the art will understand that choosing a polynomial of a larger degree will result in greater error detection. A high degree generating polynomial is necessary if it is desired to protect more, for example, than the 64K bits, or 8K bytes, that a CRC-16 can protect at one time. That is, a CRC-16 implementation will start repeating itself after 2.sup.16 shifts of the CRC register (2.sup.16 =64K bits). Therefore, with a CRC-16, there may be one byte of data in the first group of 8K bytes which has an identical CRC code in the next group of 8K bytes. On the other hand, a CRC-32 will have a unique CRC code for each of 2.sup.32 shifts of the CRC register. Therefore, with a CRC-32, 536 megabytes of contiguous data can be tested with no repeating CRC code.
Applications which require a higher level of error detection, such as some of those used by the Department of Defense, may use the following CRC-32 polynomial which has become a standard: EQU X.sup.32 +X.sup.26 +X.sup.23 +X.sup.22 +X.sup.16 +X.sup.12 +X.sup.11 +X.sup.10 +X.sup.8 +X.sup.7 +X.sup.5 +X.sup.4 +X.sup.2 +X.sup.1 +X.sup.0
While it would be possible to laboriously perform the division operation described above to obtain a checksum to be appended to data to be transferred, this approach is obviously hopelessly impractical, and "shortcuts" for determining checksums much more efficiently have been developed. Typically, in a modem or other digital transmission device, a CRC is implemented in hardware with the data manipulation carried out in a bit-by-bit operation. In larger scale digital devices and systems, hardware implementation is still usually employed because it is faster. The obvious drawback of hardware implementation of CRCs is that more hardware is required with consequent increase in cost, size and complexity and a decrease in reliability. Software implemented CRCs are known although their use is not widespread because of the speed penalty thought to be inevitable; the trade off has favored hardware. One quasi-software implementation which does enjoy good performance uses CRC routines which generate tables consisting of all possible combinations of the chosen polynomial. The checksum generation is then reduced to a table look-up. These CRC routines are considered to be the fastest software implementations available, but they take up a great deal of dedicated memory.